package com.java.comprehensive.arithmetic.leecode.easy;

/**
 * @program: comprehensive-service
 * @description: 最大子序和
 * @author: 窦绍飞
 * @create: 2021-11-19 17:19
 **/
public class LeetCode_53 {


	public static int maxSubArray(int[] nums) {

		int temp = Integer.MIN_VALUE;

		for (int i = 0; i < nums.length; i++) {
			int sum = 0;
			for (int j = i; j < nums.length; j++) {
				sum += nums[j];
				temp = Math.max(temp, sum);
			}
			System.out.println(temp);
		}
		return temp;
	}

	//暴力查找s
	public static int maxSubArrayBranch(int[] nums) {

		return maxNum(nums, 0, nums.length - 1);

	}

	//动态规划
	public static int maxSubArrayGreedy(int[] nums) {
		int result = nums[0];
		int temp = nums[0];
		for (int i = 1; i < nums.length; i++) {
			temp = Math.max(nums[i], temp + nums[i]);
			result = Math.max(temp, result);
		}

		return result;
	}

	//分治法
	private static int maxSubArrayDivideWithBorder(int[] nums, int start, int end) {
		if (start == end) {    //分治触底情况
			return nums[start];
		}

		int center = (start + end) / 2;    // 计算中间值

		/*计算子序列在整个序列左侧时的序列最大值*/
		int leftMax = maxSubArrayDivideWithBorder(nums, start, center);
		/*计算子序列在整个序列右侧时的序列最大值*/
		int rightMax = maxSubArrayDivideWithBorder(nums, center + 1, end);
		/*计算最大子序列横跨中点时的情况*/
		// 横跨中点时计算包含中点左侧最后一个元素的子序列最大值
		int leftCrossMax = Integer.MIN_VALUE; // 初始化一个值
		int leftCrossSum = 0;
		for (int i = center; i >= start; i--) {
			leftCrossSum += nums[i];
			leftCrossMax = Math.max(leftCrossSum, leftCrossMax);
		}

		// 横跨中点时计算包含中点右侧第一个一个元素的子序列最大值
		int rightCrossMax = nums[center + 1];
		int rightCrossSum = 0;
		for (int i = center + 1; i <= end; i++) {
			rightCrossSum += nums[i];
			rightCrossMax = Math.max(rightCrossSum, rightCrossMax);
		}

		// 两者加和即为横跨中点时的子序列最大值
		int crossMax = leftCrossMax + rightCrossMax;

		/* 比较三种情况，返回最大值*/
		return Math.max(crossMax, Math.max(leftMax, rightMax));
	}

	// 分治法
	public static int maxNum(int[] nums, int left, int right) {
		//递归调用 设置循环条件就是分割为一位数的时候 就是不用比较左右边界，并且中间页不用比较 最大的数
		if (left == right) {
			return nums[left];
		}
		int mid = (left + right) / 2;

		//找到分割好的左边界最大的数
		int leftMax = maxNum(nums, left, mid);
		//找到分割好的右边界最大的数
		int rightMax = maxNum(nums, mid + 1, right);


		//合成分割到最小的 数组 ，在找到他们的 中间
		int leftCrossMax = Integer.MIN_VALUE;
		int leftCrossSum = 0;
		//同理右边
		for (int i = mid; i >= left; i--) {
			leftCrossSum += nums[i];
			leftCrossMax = Math.max(leftCrossSum, leftCrossMax);
		}
		int rightCrossMax = nums[mid + 1];
		int rightCrossSum = 0;
		//计算距离 中位分界线 右边最大的连续 子序列 注意：这时候计算的
		// 如果右边第一个大 在比较中就不会被替换调 ，如果第一个小 后面有大的那么就会相加 然后连成和比较大的子序列
		//就是循环 右边的每一个数字相加 然后第一个大 还是哪几个连起来最大
		for (int i = mid + 1; i <= right; i++) {
			rightCrossSum += nums[i];
			rightCrossMax = Math.max(rightCrossSum, rightCrossMax);
		}

		//左边界 + 右边界 得到中间连起来最大的数字
		int crossMax = leftCrossMax + rightCrossMax;
		//比较 从中间开始左边界连续的子序列的和大还是右边界的大
		return Math.max(crossMax, Math.max(leftMax, rightMax));
	}

	//动态规划
	public static int dynamicPrograming(int[] nums) {
		int n = nums.length;
		for (int i = 0; i < nums.length; i++) {
			if (nums[i - 1] > 0) {
				nums[i] += nums[i - 1];
			}
		}
		return 0;
	}

	public static void main(String[] args) {
		int nums[] = {2, 1, -3, 4, -1, 2, 1, -5, 4};
		System.out.println(maxSubArrayBranch(nums));
	}

}
